🎁 Gift Package Budget Planner

Find all unique ways to partition a number using backtracking algorithm.

🎁 The Gift Budget Challenge

The Problem:

Given a budget of N, find all unique ways to spend it using different gift prices that sum to N.

Important Rules:

  • Each combination must be unique (no permutations)
  • Example: [1,2,1] and [1,1,2] are the SAME, so only [1,1,2] counts
  • Print each combination in non-decreasing order
  • Print all combinations in lexicographical order
  • All numbers must be positive integers

Input/Output Format

  • Input: Single integer N (1 ≤ N ≤ 25)
  • Output: List of all unique partitions in lexicographical order
  • Format: [[partition1], [partition2], ...]

Example 1: N = 1

Output: [[1]]

Only one way: use a single gift of price 1

Example 2: N = 4

Output: [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Explanation:
  • [1, 1, 1, 1] → Four gifts at 1 each
  • [1, 1, 2] → Two gifts at 1, one at 2
  • [1, 3] → One gift at 1, one at 3
  • [2, 2] → Two gifts at 2 each
  • [4] → One gift at 4

Visualization: Partitions of 4

[1, 1, 1, 1] → 1+1+1+1 = 4
[1, 1, 2] → 1+1+2 = 4
[1, 3] → 1+3 = 4
[2, 2] → 2+2 = 4
[4] → 4 = 4

🔄 Backtracking Strategy

Algorithm Steps

  1. Start: Begin with target N and empty partition
  2. Choose: Try adding numbers from 1 to N to current partition
  3. Constraint: Only add number if it doesn't exceed remaining sum
  4. Order: Only add numbers ≥ last number (prevents duplicates)
  5. Base Case: When remaining sum = 0, we found a valid partition
  6. Backtrack: Remove last number and try next option
  7. Result: All partitions automatically in lexicographical order

Key Insight: Avoiding Duplicates

To avoid permutations like [1,2,1] and [1,1,2]:

  • Always add numbers in non-decreasing order
  • If last number in partition is X, only try numbers ≥ X
  • This ensures [1,1,2] is generated but [1,2,1] is never considered

Pseudocode

function partition(n, start, current, result):
    if n == 0:
        result.add(copy of current)
        return
    
    for i from start to n:
        current.add(i)
        partition(n - i, i, current, result)
        current.remove_last()

Time Complexity

O(2^N)
Exponential - explores all partitions

Space Complexity

O(N)
Recursion depth and current partition

Why Backtracking?

Backtracking is perfect because:

  • We need to explore all possible combinations
  • Constraints (non-decreasing order) can be checked early
  • Can abandon paths that exceed the target sum
  • Naturally generates solutions in lexicographical order

🔍 Step-by-Step Partition Generation

Ready. Enter a number to start demo.

Generated Partitions

Click "Start Demo" to begin
Enter N and click Start Demo

Progress Tracker

1. Initialize with N
2. Start backtracking from 1
3. Try adding numbers
4. Found valid partition
5. Backtrack and try next
6. All partitions found

🎮 Generate Your Own Partitions

Enter N and press Generate Partitions

Test Cases

N = 1
Output: [[1]]
N = 4
Output: [[1,1,1,1], [1,1,2], [1,3], [2,2], [4]]
N = 5
Output: 7 partitions

📊 Algorithm Analysis

Time

O(2^N)

Number of partitions grows exponentially

Space

O(N)

Recursion depth and current partition size

Partition Count Growth

The number of partitions p(n) grows rapidly:

  • p(1) = 1
  • p(4) = 5
  • p(5) = 7
  • p(10) = 42
  • p(20) = 627
  • p(25) = 1,958

Why This Approach Works

  • Complete: Explores all possible partitions
  • Correct: Non-decreasing order prevents duplicates
  • Efficient: Prunes impossible paths early
  • Ordered: Naturally produces lexicographical order

Optimization Techniques

  1. Early Termination: Stop when remaining sum < start value
  2. Memoization: Cache results for repeated subproblems
  3. Iterative: Convert to iterative for better performance
  4. Dynamic Programming: Alternative approach for counting only

Real-World Applications

  • Finance: Ways to make change with coins
  • Resource Allocation: Distributing budgets
  • Combinatorics: Mathematical problem solving
  • Game Theory: Move enumeration
  • Data Compression: Encoding schemes